백준 알고리즘 [Baekjoon] 2473. 세 용액 [G4] n은 5000개 이하로 주어져 있다. 5000개 중 하나를 고르고, 나머지 2개는 투포인터를 활용하여 구한다. 투포인터를 활용하기 위해 정렬한다. 하나를 고른 후 s는 0 e는 n-1로 둔다. 골랐던 값이 s와 같으면 s를 1 늘리고, e랑 같으면 e를 1 줄인다. 세 수의 합이 0보다 크면 e를 1 줄인다. 세 수의 합이 0보다 작으면 s를 1 늘린다. 세 수의 합이 0이 나오면 바로 그 ... 백준 알고리즘백준 알고리즘 백준 알고리즘 13단계 (정수론 및 조합론) 1) 5086번 배수와 약수 2) 1037번 약수 아래 코드는 입력값 중 작은 값의 범위만큼 반복문을 돌며 최대 공약수를 구한다. 4) 1934번 최소 공배수 (유클리드 호제법) 이에 따라 반복문을 통해 a에는 b값을 넣어주고, b에는 a%b값을 넣어주며 b가 0이 될 때 까지 이를 반복하여 0이됐을 경우의 a값이 최대공약수가 된다. 위 3번에 내가 작성한 풀이는 불필요한 약수까지 따지게 되... 조합론백준 알고리즘문제풀이13단계정수론단계별13단계 [Baekjoon] 13549. 숨바꼭질 3 [G5] BFS로 해결한다. 현재 위치 기준 순간이동한 경우는 모두 같은 시간으로 표시한다. 큐에 수빈이의 위치와 그 때의 시간을 0으로 넣어준다. 따라서 먼저 위치마다 시간을 담을 배열을 만들어주는데 -1로 초기화 해놓는다. 확인할 값이 100000까지이니 대충 200000까지 만들어놓는다. 순간이동을 현 위치 기준 x2니까 200000보다 커지는 값이 들어올 수 없다. 시간이 안 적혀있는 경우 큐... 백준 알고리즘백준 알고리즘 BJ17144 미세먼지 안녕! 구현백준 알고리즘구현 BJ1074 Z 문제가 어려워보이기도 하지만, 재귀함수를 이용해 구현하면 생각보다 간단한 코드로 해결할 수 있다. R행 C열을 입력 받게 되면 가장 큰 Z에서 어느 부분에 속하는 지를 찾아 수를 더해주고, 한 단계씩 작은 Z로 내려가면서 이 과정을 반복해주면 된다.... 재귀함수백준 알고리즘백준 알고리즘 BJ16926 배열 돌리기 1 문제를 읽고, 배열이 돌아가는 구조를 이해한다. 각 입력을 변수와 배열에 저장한다. 다음과 같이 반시계 방향으로 각 도넛 모양의 묶음으로 배열이이 회전하게 된다. 이를 구현하기 위해서 큐에 각 도넛을 넣어준 후, 회전할 때마다 머리를 꼬리에 이어주는 방식을 사용했다. 큐를 공부한 직후라 활용했던 것으로 기억하는데, 큐를 사용하지 않고, 배열의 인덱스를 판별해 단순하게 한칸씩 당겨주는 방법이 ... 구현큐백준 알고리즘구현 [Baekjoon] 11049. 행렬 곱셈 순서 [G3] 500개까지 행렬이 주어질 수 있다. 모든 순서를 확인하면 499!까지 나오니 시간 안에 불가능하다. 따라서 dp, 메모이제이션을 활용한다. 메모이제이션으로 이차원 행렬을 만든다. 입력으로 받은 행렬을 순서대로 담고, i번째 행렬부터 j번째 행렬까지의 곱셈 연산 횟수의 최솟값을 dp[i][j]에 저장한다. i와 j의 차이가 작은 값부터 채운다. ABCD를 만드는 경우를 생각해보면, A*(BC... 백준 알고리즘백준 알고리즘 BJ17143 낚시왕 huntingShark(i); moveShark(); arrangeShark(); 각 턴마다 필요한 위 함수들을 구현해 활용했다. 상어끼리 잡아먹어 정리하는 과정에서 초기화를 잘못해주는 실수를 했고, 또, ArrayList가 아닌 LinkedList를 이용해 각 리스트 인덱스에 접근하는 시간이 많이 들어 시간초과 문제가 생기기도 했다. 문제를 푸는 데에 많은 시간이 들었지만, 덕분에 두 리스... 구현백준 알고리즘구현 BJ17471 게리맨더링 조합BFS백준 알고리즘BFS BJ2239 스도쿠 구현백준 알고리즘구현 BJ2636 치즈 토마토 문제와 거의 유사하다. BFS를 이용해서 구현하면 된다.... BFS백준 알고리즘BFS BJ7576 토마토 기본적인 BFS 문제이다. 익은 토마토를 리스트에 담아두고, BFS를 활용하여 토마토가 모두 익게 되는 일수를 출력하면 된다.... BFS백준 알고리즘BFS BJ15683 감시 이 문제는 벽과 5가지의 CCTV가 입력으로 주어지고, 씨씨티비의 방향을 적절히 정해 사각지대의 최소 크기를 구하는 것이다. CCTV를 배열에 담아두고, 각 씨씨티비의 방향을 돌려가며 모든 경우의 수를 탐색하는 방식으로 구현했다.... 완전탐색백준 알고리즘백준 알고리즘 BJ1244 스위치 켜고 끄기 스위치의 갯수와 상태를 입력 받아 배열에 저장해두기. 스위치가 조작된 횟수와 내용을 입력 받아 해결하기. 조건에 맞게 단순 구현하는 문제.... 구현백준 알고리즘구현 [Baekjoon] 12100. 2048 (Easy) [G2] 네 방향으로 이동하는 걸 총 5번 해보면 되니, 조합으로 해결한다. 조합을 만들어주는 함수 재귀함수로 조합을 구현한다. 5번 돌면 그 때 최댓값을 확인한다. 이 때 기울일 때 배열 값이 바뀌니 그걸 되돌리기 위해 [:] 얕은 복사를 활용해야 한다. 배열을 90도 시계방향으로 돌리는 함수 네 방향으로 움직이기보단 배열을 돌린다. 90도 돌렸을 때 점화식을 찾기 위해 아래와 같이 그림을 그려본다... 백준 알고리즘백준 알고리즘 [Baekjoon] 13460. 구슬 탈출 2 [G1] 10번을 움직인다. 다른 연관된 복잡도를 고려하면 시간이 더 증가하니 시간초과가 발생할 수 있다. 따라서 최적화하여, 백트래킹으로 경우의 수를 줄여나가면서 해결해본다. 먼저 빨간 공과 파란 공의 좌표를 기억한다. balls라는 2차원 배열을 만들고 빨간 공, 파란 공 순서대로 넣어준다. 4가지 방향으로 움직이며 10번 재귀를 탐색한다. 최적화를 위해 이미 나온 결과보다 더 많이 탐색하는 경우... 백준 알고리즘백준 알고리즘 백준 알고리즘 8단계 (에라토스테네스의 체) 1) 1978번 소수 찾기 따라서 입력될 값은 1000이하이기에 런타임에러가 나지 않는다면, 입력값보다 작은 정수들로 나누어 떨어지지 않는 경우를 소수로 판별했다. 2) 2581번 소수 판별 3) 11653번 소인수분해 제출해서 정답처리 될 때 까지 너무 오랜 시간이 걸린것 같았는데 런타임에러는 나지 않았다.. 4) 1929번 소수 구하기 (에라토스테네스의 체 알고리즘) 이를 통해 알게 된 ... 기본수학2단계별백준 알고리즘8단계8단계 BJ2578 빙고 빙고 게임을 진행하며, 3개 이상의 줄이 완성될 때 진행자가 부른 수를 출력하면 된다. 빙고 조건을 검사하는 함수만 잘 구현하면 된다.... 백준 알고리즘구현구현 BJ2605 줄 세우기 백준 알고리즘구현구현 BJ4485 녹색 옷 입은 애가 젤다지? 각 칸을 이동할 때마다 비용이 필요하고, 목적지로 가는 데에 최소 비용을 구하는 문제이다. DP와 BFS로 각 칸마다 필요한 최소거리를 갱신해주는 방식과 BFS나 DFS를 활용해 연산해 주는 방식이 있다. 두가지 코드를 모두 작성해보고, 어떤 이점이 있는 지 알아볼 수 있는 문제였다. 먼저 첫번째 코드는 DFS를 활용해 연산한 방식이다. 코드는 짧고 작성하기 간단하지만, 매 한칸마다 계속 연... 백준 알고리즘BFSDPBFS BJ2309 일곱 난쟁이 조합을 이용해 조건에 만족하는 경우를 찾아 출력. 기본적인 조합문제이다.... 백준 알고리즘조합백준 알고리즘 BJ1158 요세푸스 문제 문제를 이해하고, 큐를 이용해 구현하면 된다. 연결리스트를 큐처럼 활용하여 구현했다.... 백준 알고리즘큐백준 알고리즘 BJ2491 수열 증가 or 감소 수열의 최대길이를 출력하는 문제다. 증가하는 수열과 감소하는 수열의 최대길이를 각각 구해 더 큰 것을 출력한다.... 백준 알고리즘백준 알고리즘 BJ2563 색종이 도화지에 색종이를 붙혀 겹치는 부분을 고려해,붙혀진 총 넓이를 구하는 문제이다. 도화지를 boolean 배열로 구현하면 된다는 생각만 떠오른다면 쉽게 해결할 수 있다.... 백준 알고리즘백준 알고리즘 BJ2564 경비원 동근이가 시계방향 또는 반시계방향으로 이동할 때, 그 거리만 잘 계산해주면 된다. 이 문제에서는 상점의 수가 3개로 고정이기에 중첩 for문으로 구현했지만, 상점의 수가 많아지면 순열과 그 파라미터값에 거리의 합을 두는 방식으로 구현하면 될 것이다.... 백준 알고리즘구현구현 BJ2961 도영이가 만든 맛있는 음식 조합을 이용해 각 음식의 쓴 맛과 신 맛을 합연산과 곱연산으로 계산하여 두 값의 최소값을 출력하는 문제이다. 조합을 재귀함수로 구현할 수 있다면 쉽게 해결할 수 있다.... 백준 알고리즘조합백준 알고리즘 BJ3109 빵집 복잡하게 생각해 모든 경우를 다 조사하려고 하면 오히려 구현하기 어려워지고 실행시간도 길어진다. 좌측에서 우측으로 이어지는 파이프라인의 최대 수를 묻는 것이므로, 좌측의 가장 상단부터 가장 다른 파이프라인에 영향을 끼치지 않게끔 위쪽으로 이어가고, 연결이 불가능한 경우 다시 파이프라인을 설치하지 않은 상태로 복구해주면 된다.... 백준 알고리즘그리디 알고리즘그리디 알고리즘 BJ1600 말이 되고픈 원숭이 BFS를 사용해 구현하는 문제이다. 하지만 점프 횟수라는 조건 때문에 방문처리를 할 때, 점프 횟수에 따라 각각의 맵에 따로 처리를 해주어야 한다. boolean visit 배열을 3차원으로 만들어 해결해주었다.... 백준 알고리즘BFSBFS BJ14502 연구소 벽 세 개를 쌓을 수 있는 모든 경우를 찾고, 각 경우마다 바이러스를 BFS로 퍼트려 안전구역의 넓이를 구한다. 각 경우마다 구한 넓이로 최대 안전구역을 갱신한다.... 백준 알고리즘조합구현구현 이전 기사 보기
[Baekjoon] 2473. 세 용액 [G4] n은 5000개 이하로 주어져 있다. 5000개 중 하나를 고르고, 나머지 2개는 투포인터를 활용하여 구한다. 투포인터를 활용하기 위해 정렬한다. 하나를 고른 후 s는 0 e는 n-1로 둔다. 골랐던 값이 s와 같으면 s를 1 늘리고, e랑 같으면 e를 1 줄인다. 세 수의 합이 0보다 크면 e를 1 줄인다. 세 수의 합이 0보다 작으면 s를 1 늘린다. 세 수의 합이 0이 나오면 바로 그 ... 백준 알고리즘백준 알고리즘 백준 알고리즘 13단계 (정수론 및 조합론) 1) 5086번 배수와 약수 2) 1037번 약수 아래 코드는 입력값 중 작은 값의 범위만큼 반복문을 돌며 최대 공약수를 구한다. 4) 1934번 최소 공배수 (유클리드 호제법) 이에 따라 반복문을 통해 a에는 b값을 넣어주고, b에는 a%b값을 넣어주며 b가 0이 될 때 까지 이를 반복하여 0이됐을 경우의 a값이 최대공약수가 된다. 위 3번에 내가 작성한 풀이는 불필요한 약수까지 따지게 되... 조합론백준 알고리즘문제풀이13단계정수론단계별13단계 [Baekjoon] 13549. 숨바꼭질 3 [G5] BFS로 해결한다. 현재 위치 기준 순간이동한 경우는 모두 같은 시간으로 표시한다. 큐에 수빈이의 위치와 그 때의 시간을 0으로 넣어준다. 따라서 먼저 위치마다 시간을 담을 배열을 만들어주는데 -1로 초기화 해놓는다. 확인할 값이 100000까지이니 대충 200000까지 만들어놓는다. 순간이동을 현 위치 기준 x2니까 200000보다 커지는 값이 들어올 수 없다. 시간이 안 적혀있는 경우 큐... 백준 알고리즘백준 알고리즘 BJ17144 미세먼지 안녕! 구현백준 알고리즘구현 BJ1074 Z 문제가 어려워보이기도 하지만, 재귀함수를 이용해 구현하면 생각보다 간단한 코드로 해결할 수 있다. R행 C열을 입력 받게 되면 가장 큰 Z에서 어느 부분에 속하는 지를 찾아 수를 더해주고, 한 단계씩 작은 Z로 내려가면서 이 과정을 반복해주면 된다.... 재귀함수백준 알고리즘백준 알고리즘 BJ16926 배열 돌리기 1 문제를 읽고, 배열이 돌아가는 구조를 이해한다. 각 입력을 변수와 배열에 저장한다. 다음과 같이 반시계 방향으로 각 도넛 모양의 묶음으로 배열이이 회전하게 된다. 이를 구현하기 위해서 큐에 각 도넛을 넣어준 후, 회전할 때마다 머리를 꼬리에 이어주는 방식을 사용했다. 큐를 공부한 직후라 활용했던 것으로 기억하는데, 큐를 사용하지 않고, 배열의 인덱스를 판별해 단순하게 한칸씩 당겨주는 방법이 ... 구현큐백준 알고리즘구현 [Baekjoon] 11049. 행렬 곱셈 순서 [G3] 500개까지 행렬이 주어질 수 있다. 모든 순서를 확인하면 499!까지 나오니 시간 안에 불가능하다. 따라서 dp, 메모이제이션을 활용한다. 메모이제이션으로 이차원 행렬을 만든다. 입력으로 받은 행렬을 순서대로 담고, i번째 행렬부터 j번째 행렬까지의 곱셈 연산 횟수의 최솟값을 dp[i][j]에 저장한다. i와 j의 차이가 작은 값부터 채운다. ABCD를 만드는 경우를 생각해보면, A*(BC... 백준 알고리즘백준 알고리즘 BJ17143 낚시왕 huntingShark(i); moveShark(); arrangeShark(); 각 턴마다 필요한 위 함수들을 구현해 활용했다. 상어끼리 잡아먹어 정리하는 과정에서 초기화를 잘못해주는 실수를 했고, 또, ArrayList가 아닌 LinkedList를 이용해 각 리스트 인덱스에 접근하는 시간이 많이 들어 시간초과 문제가 생기기도 했다. 문제를 푸는 데에 많은 시간이 들었지만, 덕분에 두 리스... 구현백준 알고리즘구현 BJ17471 게리맨더링 조합BFS백준 알고리즘BFS BJ2239 스도쿠 구현백준 알고리즘구현 BJ2636 치즈 토마토 문제와 거의 유사하다. BFS를 이용해서 구현하면 된다.... BFS백준 알고리즘BFS BJ7576 토마토 기본적인 BFS 문제이다. 익은 토마토를 리스트에 담아두고, BFS를 활용하여 토마토가 모두 익게 되는 일수를 출력하면 된다.... BFS백준 알고리즘BFS BJ15683 감시 이 문제는 벽과 5가지의 CCTV가 입력으로 주어지고, 씨씨티비의 방향을 적절히 정해 사각지대의 최소 크기를 구하는 것이다. CCTV를 배열에 담아두고, 각 씨씨티비의 방향을 돌려가며 모든 경우의 수를 탐색하는 방식으로 구현했다.... 완전탐색백준 알고리즘백준 알고리즘 BJ1244 스위치 켜고 끄기 스위치의 갯수와 상태를 입력 받아 배열에 저장해두기. 스위치가 조작된 횟수와 내용을 입력 받아 해결하기. 조건에 맞게 단순 구현하는 문제.... 구현백준 알고리즘구현 [Baekjoon] 12100. 2048 (Easy) [G2] 네 방향으로 이동하는 걸 총 5번 해보면 되니, 조합으로 해결한다. 조합을 만들어주는 함수 재귀함수로 조합을 구현한다. 5번 돌면 그 때 최댓값을 확인한다. 이 때 기울일 때 배열 값이 바뀌니 그걸 되돌리기 위해 [:] 얕은 복사를 활용해야 한다. 배열을 90도 시계방향으로 돌리는 함수 네 방향으로 움직이기보단 배열을 돌린다. 90도 돌렸을 때 점화식을 찾기 위해 아래와 같이 그림을 그려본다... 백준 알고리즘백준 알고리즘 [Baekjoon] 13460. 구슬 탈출 2 [G1] 10번을 움직인다. 다른 연관된 복잡도를 고려하면 시간이 더 증가하니 시간초과가 발생할 수 있다. 따라서 최적화하여, 백트래킹으로 경우의 수를 줄여나가면서 해결해본다. 먼저 빨간 공과 파란 공의 좌표를 기억한다. balls라는 2차원 배열을 만들고 빨간 공, 파란 공 순서대로 넣어준다. 4가지 방향으로 움직이며 10번 재귀를 탐색한다. 최적화를 위해 이미 나온 결과보다 더 많이 탐색하는 경우... 백준 알고리즘백준 알고리즘 백준 알고리즘 8단계 (에라토스테네스의 체) 1) 1978번 소수 찾기 따라서 입력될 값은 1000이하이기에 런타임에러가 나지 않는다면, 입력값보다 작은 정수들로 나누어 떨어지지 않는 경우를 소수로 판별했다. 2) 2581번 소수 판별 3) 11653번 소인수분해 제출해서 정답처리 될 때 까지 너무 오랜 시간이 걸린것 같았는데 런타임에러는 나지 않았다.. 4) 1929번 소수 구하기 (에라토스테네스의 체 알고리즘) 이를 통해 알게 된 ... 기본수학2단계별백준 알고리즘8단계8단계 BJ2578 빙고 빙고 게임을 진행하며, 3개 이상의 줄이 완성될 때 진행자가 부른 수를 출력하면 된다. 빙고 조건을 검사하는 함수만 잘 구현하면 된다.... 백준 알고리즘구현구현 BJ2605 줄 세우기 백준 알고리즘구현구현 BJ4485 녹색 옷 입은 애가 젤다지? 각 칸을 이동할 때마다 비용이 필요하고, 목적지로 가는 데에 최소 비용을 구하는 문제이다. DP와 BFS로 각 칸마다 필요한 최소거리를 갱신해주는 방식과 BFS나 DFS를 활용해 연산해 주는 방식이 있다. 두가지 코드를 모두 작성해보고, 어떤 이점이 있는 지 알아볼 수 있는 문제였다. 먼저 첫번째 코드는 DFS를 활용해 연산한 방식이다. 코드는 짧고 작성하기 간단하지만, 매 한칸마다 계속 연... 백준 알고리즘BFSDPBFS BJ2309 일곱 난쟁이 조합을 이용해 조건에 만족하는 경우를 찾아 출력. 기본적인 조합문제이다.... 백준 알고리즘조합백준 알고리즘 BJ1158 요세푸스 문제 문제를 이해하고, 큐를 이용해 구현하면 된다. 연결리스트를 큐처럼 활용하여 구현했다.... 백준 알고리즘큐백준 알고리즘 BJ2491 수열 증가 or 감소 수열의 최대길이를 출력하는 문제다. 증가하는 수열과 감소하는 수열의 최대길이를 각각 구해 더 큰 것을 출력한다.... 백준 알고리즘백준 알고리즘 BJ2563 색종이 도화지에 색종이를 붙혀 겹치는 부분을 고려해,붙혀진 총 넓이를 구하는 문제이다. 도화지를 boolean 배열로 구현하면 된다는 생각만 떠오른다면 쉽게 해결할 수 있다.... 백준 알고리즘백준 알고리즘 BJ2564 경비원 동근이가 시계방향 또는 반시계방향으로 이동할 때, 그 거리만 잘 계산해주면 된다. 이 문제에서는 상점의 수가 3개로 고정이기에 중첩 for문으로 구현했지만, 상점의 수가 많아지면 순열과 그 파라미터값에 거리의 합을 두는 방식으로 구현하면 될 것이다.... 백준 알고리즘구현구현 BJ2961 도영이가 만든 맛있는 음식 조합을 이용해 각 음식의 쓴 맛과 신 맛을 합연산과 곱연산으로 계산하여 두 값의 최소값을 출력하는 문제이다. 조합을 재귀함수로 구현할 수 있다면 쉽게 해결할 수 있다.... 백준 알고리즘조합백준 알고리즘 BJ3109 빵집 복잡하게 생각해 모든 경우를 다 조사하려고 하면 오히려 구현하기 어려워지고 실행시간도 길어진다. 좌측에서 우측으로 이어지는 파이프라인의 최대 수를 묻는 것이므로, 좌측의 가장 상단부터 가장 다른 파이프라인에 영향을 끼치지 않게끔 위쪽으로 이어가고, 연결이 불가능한 경우 다시 파이프라인을 설치하지 않은 상태로 복구해주면 된다.... 백준 알고리즘그리디 알고리즘그리디 알고리즘 BJ1600 말이 되고픈 원숭이 BFS를 사용해 구현하는 문제이다. 하지만 점프 횟수라는 조건 때문에 방문처리를 할 때, 점프 횟수에 따라 각각의 맵에 따로 처리를 해주어야 한다. boolean visit 배열을 3차원으로 만들어 해결해주었다.... 백준 알고리즘BFSBFS BJ14502 연구소 벽 세 개를 쌓을 수 있는 모든 경우를 찾고, 각 경우마다 바이러스를 BFS로 퍼트려 안전구역의 넓이를 구한다. 각 경우마다 구한 넓이로 최대 안전구역을 갱신한다.... 백준 알고리즘조합구현구현 이전 기사 보기